package com.wu.leetcode.leetcode114;

import java.util.LinkedList;
import java.util.List;

/**
 * Leetcode114-二叉树展开为链表
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public void flatten(TreeNode root) {
        if(root==null) {
            return;
        }
        LinkedList<TreeNode> res = new LinkedList<TreeNode>();
        //前序遍历整棵二叉树
        dfs(root,res);
        TreeNode head = res.removeFirst();
        head.left = null;
        //遍历链表，将链表中的TreeNode节点前后串联起来
        while(res.size()>0) {
            TreeNode tmp = res.removeFirst();
            tmp.left = null;
            head.right = tmp;
            head = head.right;
        }
    }

    //前序遍历整棵二叉树，并将遍历的结果放到数组中
    void dfs(TreeNode root, List<TreeNode> res) {
        if(root==null) {
            return;
        }
        res.add(root);
        dfs(root.left,res);
        dfs(root.right,res);
    }
}